1. Field of the Invention
The present invention pertains to digital computing devices, and, more particularly, to a method and apparatus for managing objects having the same property.
2. Description of the Related Art
The size and complexity of modem day computing systems on the high end of the technology have exploded in recent years. As the technology matures, ever larger numbers of digital computing devices are handling ever larger amounts of data. Large scale “enterprise computing systems” can comprise tens of thousands of machines. Indeed, the Internet comprises millions of machines handling untold amounts of data. The complexity of computing systems has increased concomitantly to accommodate the data demands from so many users across so many machines in a reasonably timely fashion.
One key component in the operation of a computing system is the “operating system” (or “OS”). A general treatment of operating systems can be found in The Computer Science and Engineering Handbook, pp. 1647–1664 (Allen B. Tucker, Jr., ed. CRC Press 1997) (ISBN 0-8493-2909-4). The operating system generally controls the operation of a computing device, providing an interface between the computing device's hardware and the applications programs, e.g., word processing, spreadsheet, and e-mail software, employed by the computing device's users.
An operating system typically strives to meet at least three goals: hiding details of the hardware by creating abstractions for use by applications programs, managing computing resources (e.g., memory, processor time, input/output peripherals), and providing an effective user interface. On a personal computer level, this generally includes performing basic tasks like recognizing user input (e.g., information typed on the keyboard), transmitting output to the display, managing files and directories in the computer's disk storage, and controlling peripheral devices. On larger scale computing systems, the operating system may assume greater responsibilities like security (e.g., excluding unauthorized users) and ensuring the various users do not interfere with each other or corrupt resources common to all users.
One typical responsibility of an operating system is the management of memory. The memory system of a computing device may be categorized into disk storage (e.g., a hard disk), main memory (e.g., the random access memory, or “RAM”), and cache. Data is typically stored long term on disk storage, but it takes a relatively long time to read from or write to disk storage. If the operating system anticipates using certain data stored in disk storage, or if an application actually needs data stored in disk storage, the operating system will move it out of disk storage into main memory. Main memory is only a temporary storage, but is much quicker to read from and write to than is disk storage. Data may also be stored in cache, which is the most temporary and quickest form of memory.
One common aspect of memory management is the use of “virtual memory,” as opposed to “physical memory.” Virtual memory is an abstraction of the operating system used by application programs. The main memory has a finite number of physical addresses at which data can be stored, and is called “physical memory” in this context. However, the operating system allows applications to use a memory space that is much larger than the physical memory. This larger address space is referred to as “virtual.” The operating system maintains data structures known as a “page tables” that map virtual addresses into physical addresses and onto disk storage.
When the application writes to or reads from a virtual address, the system hardware and/or the operating system consult the page tables and translate that virtual address into a physical address. If the data is not currently in physical memory, it is read from disk—transparently to the application—and stored in physical memory. Likewise, when the operating system notices that free physical memory is getting scarce, application data is transparently written to disk storage and the associated memory is freed. This process is called “paging.” When the operating system notices that memory is so scarce that paging of individual pages is insufficient, or if application processes were inactive for a long time, it becomes more efficient to remove the whole application process from the system environment. This process is called “swapping.”
The actual swapping and paging in a virtual memory system is handled by a component of the operating system called the “modified page writer.” When a page of modified data needs to be written to the page file (i.e., swapped or paged to disk storage) the modified page writer quickly finds the appropriate page file in disk storage and a slot (i.e., free clusters) in the page file. With possibly hundreds of files to select from and millions of slots in each file, this becomes a difficult and/or time-consuming problem. The problem worsens when a large collection of pages needs to be saved, for example when a process is swapped with a large, non-compressible working set. In this case, it is not sufficient just to know that free slots exist in a given file. The data may have to be spread across several files and it is time consuming to find the most suitable files. In today's environments where terabyte sized databases and large memory systems are routinely encountered, the problems are exacerbated.
One particular operating system is the Open Virtual Memory System (“OpenVMS”). For several years, OpenVMS allowed users to create and use huge virtual address spaces, but the design still limited page file sections to a theoretical maximum of 32 Gb per process (each process could use at most 4 page files at 8 Gb) and 504 Gb total per system (63 page files at 8 Gb). While page files of this size were not common, the actually achievable/working limits for a single process, when taking into account page file use for page tables and page file use by other processes, were lower than 32 Gb. This limit was uncomfortably close to the supported maximum of physical memory on a system. Many 64-bit users often want to be able to use an amount of dynamic virtual memory larger than the amount of physical memory available on the system.
While page file sections are not the only method to access process virtual memory, they are convenient. Other methods available in OpenVMS include file based sections, PFN sections and the resident memory sections. Memory resident sections in particular are believed to become a favorite method for large memory systems. However, it is still highly desirable that OpenVMS does not impose any specific memory access methods on users. It is therefore desirable to raise page file related limits at least to an order of magnitude above physical memory limits. Ideally, a solution to this problem should support very large page and swap files each capable of holding millions of pages; support many concurrently active page and swap files; fully populate page and swap files (i e., the allocation technique should allow to find any free page); locate clusters of adjacent free pages; use a minimum amount of fixed physical memory for data structures; and be fast.
The present invention is directed to resolving, or at least reducing, one or all of the problems mentioned above.